package algorithm.t202112;

import java.util.ArrayDeque;
import java.util.HashSet;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/7 9:09
 * @description :4道
 * 大雪，2021年倒数第二个节气，平淡的一天，周末去看看租房，唉，刚通知18号四六级讲座（回头看看从准备四六级到现在已经两年了，2019.9-2021.12，时间太快）
 当时发了一个快手，标题叫回首两月面，热血未曾减。现在可以说是：回首两年面，热血未曾减。好好整，明年春招，全力以赴。跑步去。
 persevere to last
 2021.12.7
 李红磊
 2021年12月7日19:21:13
 */
public class t20211207 {

    //1034.边界着色
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int rows = grid.length, columns = grid[0].length;
        int[][] ans = new int[row][columns];
        ArrayDeque<int[]> queue = new ArrayDeque() {{
            addLast(new int[]{row, col});
        }};

        while (!queue.isEmpty()) {
            int[] poll = queue.pollFirst();
            int x = poll[0], y = poll[1];
            int count = 0;
            int[] dir = {-1, 0, 1, 0, -1};
            for (int i = 0; i < 4; i++) {
                int new_x = x + dir[i];
                int new_y = x + dir[i + 1];
                if (x < 0 || x >= rows || y < 0 || y >= columns) continue;
                if (grid[new_x][new_y] != grid[x][y]) continue;
                count++;
                if (ans[new_x][new_y] != 0) continue;
                queue.addLast(new int[]{new_x, new_y});

            }
            ans[x][y] = count == 4 ? grid[x][y] : color;
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (ans[i][j] == 0) ans[i][j] = grid[i][j];
            }
        }
        return ans;

    }

    //98.验证二叉树
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return dfs(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    private boolean dfs(TreeNode root, long upper, long lower) {
        if (root == null) return true;
        if (root.val <= lower || root.val >= upper) return false;
        return dfs(root.left, root.val, lower) && dfs(root.right, upper, root.val);

    }

    //653.两数之和4-输入BST
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return find(root, k, set);
    }

    private boolean find(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);

    }

    //235.二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return null;
    }




    public static void main(String[] args) {


    }


}
